package com.example.tree.bst;

import com.example.tree.TreeNode;

/**
 * 设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。
 * 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
 * <p>
 * 编码的字符串应尽可能紧凑。
 * 示例 1：
 * 输入：root = [2,1,3]
 * 输出：[2,1,3]
 * <p>
 * 示例 2：
 * 输入：root = []
 * 输出：[]
 * <p>
 * 提示：
 * 树中节点数范围是 [0, 104]
 * 0 <= Node.val <= 104
 * 题目数据 保证 输入的树是一棵二叉搜索树。
 * <p>
 * 注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
 */
public class Leetcode449_Codec {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(8);
        root.right.right.left = new TreeNode(7);
        root.right.right.right = new TreeNode(9);


        String str = serialize(root);
        System.out.println(str);

        TreeNode tree = deserialize(str);

    }

    // Encodes a tree to a single string.

    /**
     * 先序遍历进行序列化
     *
     * 先序遍历第一个节点就是根节点
     * BST有左子树小于根，右子树大于等于根的特性，因此确定了根节点后，再去找第一个比根节点大的元素，就是其右节点
     * @param root
     * @return
     */
    public static String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        doSerialize(root, sb);
        return sb.substring(0, sb.length() - 1);
    }

    private static void doSerialize(TreeNode root, StringBuilder sb) {
        if (root == null)
            return;

        sb.append(root.val).append(",");
        doSerialize(root.left, sb);
        doSerialize(root.right, sb);
    }


    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        if (data == null || data.length() == 0)
            return null;
        String[] strs = data.split(",");
        return doDeserialize(strs, 0, strs.length - 1);
    }

    /**
     * BST有左子树小于根，右子树大于等于根的特性，因此确定了根节点后，再去找第一个比根节点大的元素，就是其右节点
     *
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static TreeNode doDeserialize(String[] arr, int low, int high) {
        if (low > high) return null;
        TreeNode root = new TreeNode(Integer.valueOf(arr[low]));
        // 找到第一个比首元素大的元素位置
        int index = high + 1;
        for (int i = low + 1; i <= high; i++) {
            if (Integer.valueOf(arr[i]) > root.val) {
                index = i;
                break;
            }
        }
        // 递归构建子树
        root.left = doDeserialize(arr, low + 1, index - 1);
        root.right = doDeserialize(arr, index, high);
        return root;
    }
}
